package cn.javadog.algorithm.e1_100;

import java.util.Arrays;

/**
 * 加一
 * https://leetcode-cn.com/problems/plus-one/
 * @author Sprite
 */
public class Algorithm66_2 {
	public static void main(String[] args) {
		int[] digits = new int[]{9,9,9,9,9};
		int[] plusOne = plusOne(digits);
		Arrays.stream(plusOne).forEach(System.out::println);
	}

	/**
	 * 思路
	 * 从尾部遍历，逐个加1，知道不等于 9 也不可以加，时间复杂度 O(n)
	 */
	public static int[] plusOne(int[] digits) {
		for (int i = digits.length - 1; i >= 0; i--) {
			if (++digits[i] == 10) {
				digits[i] = 0;
				continue;
			}
			return digits;
		}

		// 极端情况 9999 + 1, 数组默认每一位就是0
		int[] newArr = new int[digits.length+1];
		newArr[0] = 1;
		return newArr;
	}
}
